package a2022.a20221009;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author lenovo
 * @date 2022/10/9
 */
public class b {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int time = scanner.nextInt();

        for(int i = 0;i<time;i++){
            n = scanner.nextInt();
            int m = scanner.nextInt();
            double[][] pigs = new double[n][2];
            for(int j = 0;j < n ;j++){
                pigs[j][0] = scanner.nextDouble();
                pigs[j][1] = scanner.nextDouble();
            }
            boundary = 1 << n;
            System.out.println(calc(pigs));
        }
    }
    static int n = 18;
    static int boundary = 1 << 18;
    static int calc(double[][] pigs){
        // 预处理获得 bit 数组用于表达任意两个点构成的抛物线能够消灭的猪的位运算表达
        // 对于 a > 0 非正常抛物线等价于不能消灭任何猪
        int[][] bit = getBit(pigs);

        int[] dp = new int[boundary];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        // 向前推进集合
        for(int i = 0;i < boundary ;i++){
            // 选出两个没有被消灭的猪的组合，并使用 bit 数组找到消灭后的集合，更新
            for(int j = 0;j < n ;j++){
                if(( i & (1 << j)) != 0){
                    continue;
                }
                // 先尝试单独消灭这只猪
                int t = i | (1 << j);
                dp[t]= Math.min(dp[t] ,dp[i] + 1);
                for(int k = j+1;k<n;k++){
                    if((i & (1 << k)) != 0){
                        continue;
                    }
                    int next = i | bit[j][k];
                    dp[next] = Math.min(dp[i]+1,dp[next]);
                }
            }
        }
         return dp[boundary - 1];
    }

    static int[][] getBit(double[][] pigs){
        int[][] result = new int[n][n];
        for(int i = 0;i<n;i++){
            for (int j = i+1;j < n;j++){

                double x1 = pigs[i][0];
                double y1 = pigs[i][1];
                double x2 = pigs[j][0];
                double y2 = pigs[j][1];

                double a = (y1*x2 - y2*x1)/(x1*x2*(x1-x2));
                if(a >= 0){
                    continue;
                }
                double b = (y1*x2*x2 - y2*x1*x1)/(x1*x2*(x2-x1));
                // 遍历所有的点，如果存在于该直线上则加入集合
                int set = 0;
                for(int k = 0;k < n;k++){
                    double x = pigs[k][0];
                    double y = pigs[k][1];
                    double expect = x*x*a+x*b;
                    if(Math.abs(expect-y) < 1e-6){
                        set |= 1<<k;
                    }
                }
                result[i][j] = set;
            }
        }
        return result;
    }
}
//
//        3
//        2 0
//        1.41 2.00
//        1.73 3.00
//        3 0
//        1.11 1.41
//        2.34 1.79
//        2.98 1.49
//        5 0
//        2.72 2.72
//        2.72 3.14
//        3.14 2.72
//        3.14 3.14
//        5.00 5.00